/**
 * https://leetcode.cn/submissions/detail/585286845/
 * 3249. 统计好节点的数目
 * Medium, 黄伟杰 2024.12.05
 * DFS
 */

class Solution
{
public:
    int countGoodNodes(vector<vector<int>> &edges)
    {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x); // 建图
        }

        int ans = 0;
        auto dfs = [&](auto dfs, int x, int fa) -> int
        {
            int size = 1, er1 = 0; // 自身大小，第一个子树大小
            int cnt = 1;
            for (int y : g[x])
            {
                if (y == fa)
                    continue;
                int sz = dfs(dfs, y, x);
                if (er1 == 0)
                    er1 = sz;
                else if (sz != er1) // 不同不+1
                    cnt = 0;
                size += sz;
            }
            ans += cnt;
            return size;
        };
        dfs(dfs, 0, -1);
        return ans;
    }
};